class Solution {
    public int cuttingRope(int n) {
        if(n<4){
            return n-1;
        }
        int [] arr=new int [n+1];
        arr[1]=0;
        arr[2]=1;
        arr[3]=2;
        for(int i=4;i<n;i++){
            for(int j=1;j<i/2;j++){
                arr[i]=Math.max(arr[i],j*arr[i-j]);
            }
        }
        return arr[n];
    }
    public int minArray(int[] numbers) {
        //二分查找
        int left=0;
        int right=numbers.length-1;
        int mid=0;
        while(left<right){
            mid=(left+right)/2;
            if(numbers[mid]>numbers[right]){//旋转点在右边
                left=mid+1;
            }else if(numbers[left]>numbers[mid]){
                right=mid;
            }else{
                right--;
            }
        }
        return numbers[left];
    }
    public int fib(int n) {
        if(n<=1){
            return n;
        }
        int [] arr=new int [n+1];
        arr[0]=0;
        arr[1]=1;
        for(int i=2;i<arr.length;i++){
            int len=arr[i-1]+arr[i-2];
            arr[i]=len% 1_0000_0000_7;
        }
        return arr[n];
    }
    public  int i=0;
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //前序和中序构建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int []preorder,int []inorder,int start,int end){
        if(start>end){
            return  null;
        }
        TreeNode root=new TreeNode(preorder[i]);
        int index=findIndex(inorder,start,end,preorder[i]);
        if(index==-1){
            return null;
        }
        i++;
        root.left=buildTreeChild(preorder,inorder,start,index-1);
        root.right=buildTreeChild(preorder,inorder,index+1,end);
        return root;
    }
    public int findIndex(int [] inorder,int start,int end,int target){
        for(int i=start;i<=end;i++){
            if(inorder[i]==target){
                return i;
            }
        }
        return -1;
    }
}